//给你一个满足下述两条属性的 m x n 整数矩阵： 
//
// 
// 每行中的整数从左到右按非严格递增顺序排列。 
// 每行的第一个整数大于前一行的最后一个整数。 
// 
//
// 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
// 
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
//输出：true
// 
//
// 示例 2： 
// 
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 100 
// -10⁴ <= matrix[i][j], target <= 10⁴ 
// 
//
// Related Topics 数组 二分查找 矩阵 👍 887 👎 0


package com.tyrone.leetcode.editor.cn;

public class SearchA2dMatrix {
    public static void main(String[] args) {
        Solution solution = new SearchA2dMatrix().new Solution();
//        int[][] arr = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        int[][] arr = {{1},{3}};
        System.out.println(solution.searchMatrix(arr, 3));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 分两次二分
         * @param matrix
         * @param target
         * @return
         */
        public boolean searchMatrix(int[][] matrix, int target) {
            int l=0,r = matrix.length-1;;
            while (l<r){
                int mid = l+r+1>>1;
                if (matrix[mid][0]<= target){
                    l = mid;
                }else {
                    r = mid-1;
                }
            }
            int row = r;
            if (matrix[row][0] == target ) return true;
            if (matrix[row][0] > target) return false;
            l = 0; r = matrix[0].length - 1;
            while (l<r){
                int mid = l + r + 1 >> 1;
                if (matrix[row][mid] <= target) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            int col = r;
            return matrix[row][col] == target;
        }

//        public boolean searchMatrix(int[][] matrix, int target) {
//
//            int left = 0 ;
//            int col = matrix[0].length;
//            int right = matrix.length-1;
//            while (left<right){
//                int mid = (right-left)/2;
//                if (matrix[mid][col]>target){
//                    right = rowMid;
//                }
//            }
//            return false;
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}